package leetcode.每日一题;

import leetcode.util.CommonUtils;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/20 16:40
 * @description：https://leetcode-cn.com/problems/the-time-when-the-network-becomes-idle/
 */
public class 网络空闲的时刻 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.networkBecomesIdle(
                new int[][]{{3, 12}, {15, 3}, {10, 14}, {12, 10}, {13, 5}, {4, 2}, {16, 17}, {8, 16}, {7, 6}, {0, 15}, {11, 7}, {1, 11}, {2, 8}, {2, 16}, {14, 13}, {6, 4}, {5, 1}, {17, 9}},
                new int[]{0, 2, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 3, 1}));
        // System.out.println(solution.networkBecomesIdle(new int[][]{{0, 1}, {1, 2}, {0, 2}}, new int[]{0, 10, 10}));
        // System.out.println(solution.competeTime(new int[]{0, 5, 2, 4, 1, 4, 1, 1, 5, 2, 3, 3, 3, 2, 4}, new int[]{0,4,100,100,100,100,100,100,100,100,100,100,100,100,100}));

    }

    class Solution {
        public int networkBecomesIdle(int[][] edges, int[] patience) {
            int n = patience.length;
            List<Integer>[] lists = new List[n];
            for (int i = 0; i < n; i++) {
                lists[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                lists[edge[0]].add(edge[1]);
                lists[edge[1]].add(edge[0]);
            }
            int step = 1;
            int max = 0;
            Queue<Integer> queue = new LinkedList<>();
            boolean[] visit = new boolean[n];
            queue.offer(0);
            visit[0] = true;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int cur = queue.poll();
                    for (int next : lists[cur]) {
                        if (visit[next]) {
                            continue;
                        }
                        queue.offer(next);
                        visit[next] = true;
                        // 最后一次发送的时间
                        int tailTime = patience[next] * ((2 * step - 1) / patience[next]);
                        // 总时间
                        int time = tailTime + 2 * step + 1;
                        max = Math.max(max, time);
                    }
                }
                step++;
            }
            return max;
        }
    }


    /*class Solution {
        public int networkBecomesIdle(int[][] edges, int[] patience) {
            int n = patience.length;
            int[] minTimePath = new int[n];
            List<Integer>[] gaps = new List[n];
            for (int i = 0; i < n; i++) {
                gaps[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                gaps[edge[0]].add(edge[1]);
                gaps[edge[1]].add(edge[0]);
            }
            bfs(gaps, minTimePath);
            System.out.println(Arrays.toString(minTimePath));
            return competeTime(minTimePath, patience);
        }

        private int competeTime(int[] minTimePath, int[] patience) {
            int max = 0;
            int n = patience.length;
            for (int i = 1; i < n; i++) {
                int time = minTimePath[i] * 2;
                if (time < patience[i]) {
                    max = Math.max(max, time + 1);
                    continue;
                }
                // 最大空闲时间 = 最后一次发送时间 + 一次来回的时间
                // 总共发送次数 0秒的不算
                int nums = time / patience[i] - 1;
                nums = nums + (time % patience[i] == 0 ? 0 : 1);
                // 最后一次发送的时间
                int tailTime = nums * patience[i];
                // 最大空闲时间
                int maxFreeTime = tailTime + time;
                max = Math.max(max, maxFreeTime + 1);
            }
            return max;
        }

        private void bfs(List<Integer>[] gaps, int[] minTimePath) {
            int n = minTimePath.length;
            boolean[] visit = new boolean[n];
            visit[0] = true;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            int step = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int cur = queue.poll();
                    for (int next : gaps[cur]) {
                        if (visit[next]) {
                            continue;
                        }
                        queue.offer(next);
                        visit[next] = true;
                        minTimePath[next] = step;
                    }
                }
                step++;
            }
        }
    }*/
}
